1. Field of the Invention
The present invention concerns a method and a device for coding and transmission using a sub-code of a product code.
The object of the present invention is to combat errors appearing during the transmission of information, notably within the context of wireless transmission. This is because the transmitted signals, notably those of an electrical nature, are disrupted by noise.
2. Description of the Related Art
A message is defined as being a digital sequence.
One solution consists of making the message redundant, that is to say adding redundancy into the message: in other words, in addition to the symbols representing the information, symbols are transmitted which are functions of the said symbols representing the information.
A device which produces a sequence in an alphabet is called a coder.
A set of sequences produced by the coder is called a code.
To specify a code, or to specify the way of calculating the redundancy to be appended to an item of information, use is often made of matrices. For example, if it is wished to append redundant symbols (v4, v5, v6) (the number of redundant symbols is three in this example) to k binary information symbols (v0, v1, v2, v3) (the number of binary information symbols is denoted k and is equal to four in this example), in order to form the word v=(v0, . . . , v6) of length n (n is equal to seven in this example), a matrix H with n columns and nxe2x88x92k rows (three in this example) in the alphabet {0, 1} is produced, such that for example       H    =          "LeftBracketingBar"                                    1                                1                                1                                0                                1                                0                                0                                                0                                1                                1                                1                                0                                1                                0                                                1                                1                                0                                1                                0                                0                                1                              "RightBracketingBar"        ,
and the binary word v of length seven is made to satisfy the equation vi*Hr=0, where xe2x80x9c*xe2x80x9d designates the matrix product, where Hr designates the transposed matrix of the matrix H and where the additions are performed modulo 2: the word v is then said to be orthogonal to the matrix H. In this example, the redundant symbols v4, v5 and v6 are therefore calculated as follows;
v4=v0+v1+v2
v5=v1+v2+v3
v6=v0+v1+v3.
The parameter n is called the code length and the parameter k, which is always strictly less than the parameter n, is called the code dimension. The matrix H used in this way is called the parity control matrix or parity matrix.
It is well known that this coding method makes it possible to correct one error: if, after having sent the binary word v on a noisy channel, the binary word r=(r0, . . . , r6) is received where, for at most one index i, one of the symbols ri is different from the symbol vi, the correction of this error is possible (see Peterson and Weldon, xe2x80x9cError-Correcting Codesxe2x80x9d MIT Press). More generally, for a fairly large parameter n, more efficient codes can be obtained by increasing the value of the parameter nxe2x88x92k. Such codes make it possible to correct more than one erroneously received symbol. A tool of choice in the implementation of such codes, referred to as linear codes, is then the syndrome s=r*Hr corresponding to the received word r (cf. the Peterson and Weldon reference cited above).
With the aim of improving the transmission performance by means of a coding allowing error correction, without increasing the complexity of its implementation xe2x80x9ctoo muchxe2x80x9d, the product code idea is resorted to: a message to be transmitted which has k*k symbols constituting the information is considered. These symbols are disposed at the top left in a square table of dimension n*n: the first k places of the first k rows of the table have thus been filled, counting the places in the rows from the left and counting the rows in the table from the top. The other nxe2x88x92k places in each row of the table are filled by redundant symbols which depend only on the first k symbols in the row in question: the first k rows of the table or in other words the first k places of each column have thus been entirely filled, counting the places in the columns from the top. The other nxe2x88x92k places in each column of the table are filled by redundant symbols which depend only on the first k symbols in the column in question: the table has thus been entirely filled.
In order to decode a message which comes in the form of a product code, a start can be made by decoding the rows, and the corrections made, if necessary. Then, with the corrected data, the columns are decoded and the corrections made. The method can thus be iterated.
A hard iterative decoding method based on hard demodulation is considered in the article xe2x80x9cDiagonals of 2D-Abelian codesxe2x80x9d by J. Lacan, published in the proceedings of the 1998 Information Theory Workshop, pp 110-111.
Another improvement of the transmission performance is possible by resorting to a so-called soft decision demodulation method. With this method, a received symbol, denoted rand corresponding to a symbol sent in the alphabet {0, 1}, is no longer interpreted as an element of this alphabet {0, 1}. The information , provided by the symbol r and which can be used by a decoder, is then expressed by the formula =log[f(r)] where log designates the logarithm of its argument in a base strictly greater than 1, and where f(r) is the ratio between the likelihood of receiving a value close to r when 1 is sent and that of receiving a value close to r when 0 is sent. This logarithm is called the log-likelihood-ratio (l.l.r.).
When such a soft decision can be made, the decoding of product codes proves to be particularly efficient (see on this subject: J. Hagenauer, E. Offer and L Papke, xe2x80x9cIterative decoding of binary block and convolutional codesxe2x80x9d, IEEE Transactions on Theory, vol. 42, pp 429-445, March 1996 and R. Pyndiah, A. Glavieux, A. Picart and S. Jacq, xe2x80x9cNear optimum decoding of product codesxe2x80x9d, Proceedings IEEE Globecom Conference, pp 339-343, San Francisco, November 1994). The theoretical ideas at the basis of these articles date back to the book by R. G. Gallager, xe2x80x9cLow-density parity-check codesxe2x80x9d, published by MIT Press in 1963, but the above articles succeed in specifying how to implement these theoretical bases efficiently.
In practice, the letters of the alphabet {0, 1} are transmitted on the channel by two different electrical signals and identified with the numbers +1 (for the letter 0) and xe2x88x921 (for the letter 1). As long as the electrical signals chosen in this way are xe2x80x9creasonablexe2x80x9d and the noise affecting the channel not too different from the conventional Additive White Gaussian Noise, better known by the initials AWGN, the situation of such a channel is well known and commonly studied.
To illustrate the usage of the ideas introduced above, this particular simple example is considered. The control matrix H=[1 1 1] defines a code (n=3, k=2) in the alphabet {0, 1}. By applying the construction mentioned above of product code of this code by itself, four binary symbols v0,0v0,1, v1,0 and v1,1, can be used to construct the binary word v of length 9 represented by this particular 3*3 matrix:   v  =                              v                      0            ,            0                                                v                      0            ,            1                                                v                      0            ,            2                                                        v                      1            ,            0                                                v                      1            ,            1                                                v                      1            ,            2                                                        v                      2            ,            0                                                v                      2            ,            1                                                            v                          2              ,              2                                ,                    
where the symbols v2,0, v2,1, v2,2, v0,2 and v1,2 have been calculated so that the three rows and the three columns of the word v are orthogonal to the matrix H.
By virtue of the parity relationships imposed by the matrix H on these symbols vi,j, it may be concluded that v1,1 (for example) satisfies the equations:
v1,1=v0,1+v1,2xe2x80x83xe2x80x83(1)
v1,1=v0,1+v2,1xe2x80x83xe2x80x83(2)
where the additions are performed modulo 2. After transmission of a symbol vij on the channel, a calculation can be performed, for the received symbol rij which corresponds to it, of the log-likelihood-ratio ij=[log f(rij)], and the matrix  of these values i,j can be constructed:   𝒥  =                              𝒥                      0            ,            0                                                𝒥                      0            ,            1                                                𝒥                      0            ,            2                                                        𝒥                      1            ,            0                                                𝒥                      1            ,            1                                                𝒥                      1            ,            2                                                        𝒥                      2            ,            0                                                𝒥                      2            ,            1                                                𝒥                      2            ,            2                              
The equations (1) and (2) above express the fact that the symbol v1,1 (for example) can be estimated from three sets of values ij independent from one another. The first such set is the set {11}, the second is the set {1,0, 1,2} by virtue of the equation (1) and the third is the set {0,12,1} by virtue of the equation (2). More generally, whatever the coordinates s and t, there are, for estimating the symbol vs,t, three sets of values i,j, the first of which is the singleton {s,t}, and the other two of which each contain two elements. The use of these independent sets of i,j for estimating the symbols vs,t of the transmitted word v on the basis of the received symbols ri,j and the corresponding table of values i,j can be understood by referring for example to J. Hagenauer et al. (reference given above). A general case is considered here where the parameter n can be greater than or equal to three and the parameter k can be greater than or equal to two. However, for any pair of coordinates (s,t) of a symbol vs,t, only three sets of values i,j are to be taken into consideration, namely the set {s,t}, the set {s,u for u different from t} and the set {u,t for u different from s}.
In this context, the iterative correction of a received word r can be performed as follows.
In a first step, for any pair of coordinates (s, t), the element s,t of the matrix  and the set {s,u for u different fron t} are considered. This makes it possible to calculate from these data, for any pair of coordinates (s, t), a new log-likelihood-ratio denoted s,t 
In a second step, for any pair of coordinates (s, t), the element s,t of the matrix , the element s,t which has just been calculated and the set {u,t, for u different from s} are considered. After having set Ks,t=s,t, a new log-likelihood-ratio again denoted s,t can then be calculated for any pair of coordinates (s, t).
In a third step, for any pair of coordinates (s, t), the element s,t of the matrix , the element s,t which has just been calculated and the set {s,u for u different from t} are considered. After having set Ks,t=s,t, a new log-likelihood-ratio again denoted s,t an then be calculated for any pair of coordinates (s, t).
The procedure is then continued by performing the second and third steps alternately When the number of steps chosen beforehand has been performed, three matrices containing log-likelihood-ratios are available. The first is the matrix , the second is the matrix  having the element s,t in coordinate position (s, t) and the third is the matrix K having the element Ks,t in coordinate position (s, t).
The matrix =++K is then calculated and the following are used for the decoding: if i,j is positive, the estimate vi,j=1 is used, and if i,j is negative, the estimate vi,j=0 is used. Furthermore, the absolute value of i,j expresses the degree of confidence which can be given to this decision.
The J. Hagenauer et al. reference given above will advantageously be consulted on this subject.
The context of product codes is, as has been seen, particularly adapted to iterative correction. The words of such a code C are easily represented by means of a rectangular table with Nh columns and Nv rows, where each row (respectively each column) is a word of a code Ch (respectively Cv) of length Nh (respectively Nv). A word of the code C of length Nh*Nv is thus represented by the matrix:                     v        =                                                            v                                  0                  ,                  0                                                                                    v                                  0                  ,                  1                                                                    …                                                      v                                  0                  ,                                      Nh                    -                    1                                                                                                                          v                                  1                  ,                  0                                                                                    v                                  1                  ,                  1                                                                    …                                                      v                                  1                  ,                                      Nh                    -                    1                                                                                                          …                                      …                                      …                                      …                                                                          v                                                      Nv                    -                    1                                    ,                  0                                                                                    v                                                      Nv                    -                    1                                    ,                  1                                                                    …                                                      v                                                      Nv                    -                    1                                    ,                                      Nh                    -                    1                                                                                                          (        3        )            
where each vi,j is a binary symbol intended to be transmitted.
After transmission of the word v by the channel, a word r is received:                     r        =                                                            r                                  0                  ,                  0                                                                                    r                                  0                  ,                  1                                                                    …                                                      r                                  0                  ,                                      Nh                    -                    1                                                                                                                          r                                  1                  ,                  0                                                                                    r                                  1                  ,                  1                                                                    …                                                      r                                  1                  ,                                      Nh                    -                    1                                                                                                          …                                      …                                      …                                      …                                                                          r                                                      Nv                    -                    1                                    ,                  0                                                                                    r                                                      Nv                    -                    1                                    ,                  1                                                                    …                                                      r                                                      Nv                    -                    1                                    ,                                      Nh                    -                    1                                                                                                          (        4        )            
from which the matrix  of the elements i,j=log[f(ri,j)] can therefore be calculated.
The aim of the present invention is to improve the efficiency of the transmission, of the correction and of the decoding by explicitly implementing coding methods using codes for which it is possible to obtain more than three independent sets of symbols providing information on any one of the symbols of the word v.
The codes to be used in the present invention are not however usual product codes. They are more precisely codes contained in these usual product codes, that is to say sub-codes of these usual product codes. An attempt is made to obtain a code which makes it possible to obtain more than three independent estimates for each transmitted symbol. It will be made certain that redundancies exist not only on the rows and the columns, but also on the diagonals with certain gradients.
The present invention is concerned with the turbodecoding of these codes, i.e. with an iterative decoding that uses soft information at each step.
To this end, according to a first aspect, the present invention relates to a method of transmitting information representing a physical quantity and represented by first binary symbols, having:
a coding operation comprising an operation of calculating second binary symbols, referred to as calculated binary symbols, from the said information, the said calculated binary symbols being provided in order to be disposed in a square table,
an operation of transferring the said calculated symbols, comprising an operation of modulating the said calculated symbols and an operation of demodulating the modulated symbols into symbols referred to as received symbols,
an operation of correcting the said received symbols providing binary symbols referred to as corrected symbols, and
an operation of decoding the information from the said corrected symbols,
characterised in that, for each said calculated binary symbol, there exist at least three distinct diagonals in the table which contain this calculated binary symbol and which, deprived of this calculated binary symbol, still allow each one on its own to recalculate the said calculated binary symbol,
the demodulating operation in performed by a soft decision method, and
the correcting operation is performed iteratively with respect to each of the distinct diagonals.
In a preferred embodiment, the present invention also relates to a method such as exposed briefly above, characterised in that the calculating operation comprises:
an operation of defining a plurality of bivariable polynomials representing the first binary symbols as their coefficients, and
an operation of calculating the calculated binary symbols in the form of coefficients of a polynomial obtained as a sum of products of each one of the defined polynomials and a respective one of a plurality of predetermined basis polynomials which form a basis of the set of all bivariable polynomials.
In the sense of the present invention, a row and a column of a matrix are special diagonals. Such a method makes it possible to have available at least three independent sources of data on the calculated binary symbol, besides the calculated binary symbol itself. By means of this coding method, the redundancy of the coded message is increased judiciously and without excess. In this way, the performance of the correction and of the decoding and therefore of the transmission are improved, by making error correction possible without increasing too much either the redundancy, or the complexity of implementation of the coding and decoding.
This is because, as mentioned in J. Hagenauer et al. (reference given above) the quantities ()s,t and (K)s,t introduced above become more and more correlated at each iteration.
According to the invention, it is worthwhile, notably for remedying this drawback, to have available more than three disjoint sets of values i,j for estimating each of the symbols vs,t.
This is because, at the third step mentioned above, use has been made again of the step {s,u for u different from t} which had already been used at the first step. If, besides the value s,u the set {s,u for u different from t} and the set {u,t for u different from s}, other sets were available, disjoint from these first three, disjoint in pairs and providing information on the symbol vs,t, the first of them could for example be used at the third step, the second of them at the fourth step and so on. If, therefore, for any pair of coordinates (s,t) there are available, besides the value s,t, xcex such disjoint sets of values i,j, not containing the value s,t but each making it possible to correctly estimate the symbol vs,t in the absence of noise, xcex steps can be performed, in the iterative correction procedure briefly outlined above, before having to use one of these xcex sets a second time. At each of these steps, it is then necessary to store, for any coordinate s and for any coordinate t, not only the last value s,t calculated, but also the last xcexxe2x88x921.
When the number of steps chosen beforehand has been performed, there are then available xcex+1 matrices containing logarithms of likelihood-ratios. The first is the matrix  and the xcex others are the last xcex matrices  produced by the algorithm. The matrix is then calculated as being the sum of these xcex+1 matrices and it is used as indicated above.
It should also be noted that if, besides the symbol rs,t itself, there are available at least three disjoint sets of values i,j for estimating each symbol vs,t, the solution to the well known problem of rectangular error configurations mentioned in column 2 of page 441 in the above-mentioned article by J. Hagenauer et al. is improved.
In a preferred embodiment of the transmission method, the decoding operation comprises:
an operation of calculating product polynomials by multiplying a polynomial representing the corrected symbols and each of the predetermined polynomials,
an operation of estimating the first binary symbols as the coefficients of the defined polynomials on the basis of specific coefficients of the product polynomials, and
an operation of outputting the estimated coefficients as the decoded information.
In a preferred embodiment of the transmission method, the correcting operation determines a respective log-likelihood-ratio and the corected symbols are estimated on the basis of a sum of the respective log-likelihood-ratios.
In a preferred embodiment, for the transmission method, during the calculation operation, there exists an Abelian code such that, for any information, the table of calculated binary symbols is a word of the said Abelian code.
The advantage of using an Abelian code comes from the fact that efficient calculation tools are available, provided by the theory of Abelian codes, for effectively specifying these codes and the corresponding coders. This theory is notably studied by P. Delsarte, in xe2x80x9cAutomorphisms of Abelian codesxe2x80x9d, Philips Research Reports, vol. 25, pp 389-403, 1970 and by H. Imai, xe2x80x9cA theory of two-dimensional cyclic codesxe2x80x9d, Information and Control, vol. 34, pp 1-21, 1977.
In a preferred embodiment, the transmission method is such that there exists an integer n greater than or equal to two, such that, during the calculation operation, for an element r which is null or infinite or an integer prime with n, each diagonal of gradient r is a word of a BCH code
Which means that, for a given value of gradient, each diagonal which has this gradient is a word of a BCH code The BCH codes are notably defined in the Peterson and Weldon book mentioned above.
The advantage of using diagonals which are in a BCH code is twofold. On the one hand, these codes being cyclic, they fit perfectly in the Abelian code structure mentioned above, on the other hand these BCH codes are known as being amongst the best and most practical cyclic codes (see on this subject the book by S. Lin and D. Costello, xe2x80x9cError Control Coding: Fundamental and Applicationsxe2x80x9d, Prentice-Hall, 1983).
Advantageously, the transmission method can be designed so that there exists an integer m greater than or equal to 2, an integer n equal to 2mxe2x88x921 and an integer k equal to nxe2x88x92m, such that, during the calculation operation, for an element pe which is null or infinite or an integer prime with the integer n, each diagonal of gradient pe is a word of a Hamming code of type (n,k).
Which means that, for a given value of gradient, each diagonal which has this gradient is a word of a Hamming code of type (n,k).
The advantage of using a diagonal which is in a Hamming code is twofold. On the one hand the efficiency of a Hamming code is relatively high, which is a favourable element for the efficiency of the overall Abelian code in which this Hamming code is used. On the other hand, the decoding of Hamming codes in a manner adapted to the aim of the present invention is performed quite simply (see the article by Hagenauer et al. mentioned above).
For analogous reasons, advantageously, the transmission method is such that there exists an integer m greater than or equal to 2, an integer n equal to 2mxe2x88x921 and an integer k equal to nxe2x88x92m, such that, during the calculation operation, for at least two elements p and q, with p null or infinite or an integer prime with the integer n and q null or infinite or an integer prime with the integer n, each diagonal of gradient p and each diagonal of gradient q is a word of one and the same Hamming code of type (n,k).
Which means that, for at least two distinct values of gradient, the diagonals of the tables of binary symbols which have these gradients are words of a Hamming code of type (n,k).
This makes it possible to have the advantages of Hamming codes.
Advantageously, the transmission method briefly explained above is such that there exists at least one integer n greater than or equal to two, such that, during the calculation operation, for an element s which is null or infinite or an integer prime with the integer n, each diagonal of gradient s is a word of the parity code of type (n, nxe2x88x921).
Which means that, for one or more values of gradient, the diagonals which have this gradient are in the parity code of type (n, nxe2x88x921) defined as being the set of binary words of length n containing an even number of is.
This makes it possible to keep quite a high efficiency in the overall Abelian code without reducing the number of disjoint sets of values i,j used for the decoding of each symbol vs,t.
The invention also relates to a device employing a transmission method such as that briefly presented previously.
The invention also relates to a camera, a facsimile machine, photographic apparatus, and a computer, characterised in that they include a device as briefly described above.
The invention also relates to:
an information storage means readable by a computer or a microprocessor storing instructions of a computer program, characterised in that it allows the implementation of the method of the invention briefly described above, and
an information storage means readable by a computer or a microprocessor storing data resulting from the implementation of the method briefly described above.
The invention also relates to:
an information storage means which is removable, partially or totally, and readable by a computer or a microprocessor storing instructions of a computer program, characterised in that it allows the implementation of the method of the invention as briefly described above, and
an information storage means which is removable, partially or totally, and readable by a computer or a microprocessor storing data resulting from the implementation of the method briefly described above.
The preferential or particular characteristics and the advantages of this transmission method, of these devices, of this camera, of this facsimile machine, of this photographic apparatus, of this computer and of these information storage means being identical to those of the coding method, these advantages are not repeated here.